// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-07 10:52
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;
import com.DataStruct.Tree.TwoBinaryTree.Utils;
import org.junit.jupiter.api.Test;

@SuppressWarnings("AlibabaRemoveCommentedCode")
public class IsSubtree {

    /**
     * 判断一棵二叉树是否是另一棵树的子树
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        return serach(root, subRoot);
    }


    private boolean serach(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root.val == subRoot.val) {
            if (isSame(root, subRoot)) {
                return true;
            }
        }
        if (root.left != null) {
            if (serach(root.left, subRoot)) {
                return true;
            }
        }
        if (root.right != null) {
            if (serach(root.right, subRoot)) {
                return true;
            }
        }
        return false;
    }


    /**
     * 判断两棵子树是否相等 -> 遍历实现
     *
     * @param root
     * @param subRoot
     */
    private boolean isSame(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            // 两棵树都为空
            return true;
        }
        if (root == null || subRoot == null) {
            // 两个树中有一棵树是空树
            return false;
        }
        // 两棵树的当前节点都不为空
        if (root.val != subRoot.val) {
            // 当前节点的值不相同
            return false;
        }
        // 左右子树也相同则两棵树相同
        return isSame(root.left, subRoot.left) && isSame(root.right, subRoot.right);
    }


    @Test
    public void shout() {
        Utils utils = new Utils();
        int[] nodesT = {3, 4, 5, 1, 2};
        int[] nodesO = {4, 1, 2};
        TreeNode<Integer> root1 = utils.constructTreeBySequence(nodesO);
        TreeNode<Integer> root2 = utils.constructTreeBySequence(nodesT);
//        System.out.println(isSame(root1, root2));
        System.out.println(isSubtree(root1, root2));
    }

}
